Ngay sau khi Cách mạng tháng 8 nổ ra, các lãnh đạo Việt Minh đã cho thành lập nhiều đơn vị cảnh sát ở các địa phương để giữ gìn trật tự trên cơ sở các đội tự vệ của Việt Minh. Tuy nhiên, lực lượng này chưa có tên gọi chung: ở Bắc Bộ có tên là Sở Liêm phóng, ở Trung Bộ là Sở trinh sát và ở Nam Bộ là Quốc gia tự vệ cuộc. Mãi đến đầu năm 1946, theo Sắc lệnh số 23/SL ngày 21 tháng 2 năm 1946 của Chủ tịch Hồ Chí Minh, các đơn vị cảnh sát này được hợp nhất dưới tên gọi Việt Nam Công an vụ, đặt dưới quyền quản lý của Bộ Nội vụ. Theo Sắc lệnh này, "Việt Nam Công an vụ sẽ do một ông Giám đốc điều khiển, dưới quyền chỉ huy trực tiếp của Bộ Nội vụ. Ông Giám đốc có thể có một Phó Giám đốc giúp việc. Những chức chánh, phó Giám đốc Việt Nam Công an vụ sẽ do Sắc lệnh của Chủ tịch Chính phủ Việt Nam bổ nhiệm theo lời đề nghị của Bộ trưởng Bộ Nội vụ".[1] Chỉ một ngày sau, ông Nguyễn Dương được bổ nhiệm vào chức vụ đứng đầu ngành Công an Việt Nam với chức vụ Giám đốc Việt Nam Công an vụ.[2]
Ngày 18 tháng 4 năm 1946, Bộ trưởng Nội vụ Huỳnh Thúc Kháng đã ký Nghị định 121–NV/NĐ, quy định tổ chức ngành Công an vụ thành 3 cấp:
Cấp trung ương gọi là Nha Công an Việt Nam
Cấp kỳ có tên gọi là Sở Công an Kỳ
Cấp tỉnh có tên gọi là Ty Công an Tỉnh
Cũng theo Nghị định trên, "Cơ quan công an trung ương đặt dưới quyền điều khiển trực tiếp của ông Tổng giám đốc Việt Nam công an vụ.". Giúp việc cho Tổng giám đốc Việt Nam công an vụ là một Phó giám đốc.[3] Ngày 2 tháng 5 năm 1946, ông Lê Giản được bổ nhiệm làm Phó giám đốc Việt Nam Công an vụ.[4].
Ngày 8 tháng 6 năm 1946, Chủ tịch Hồ Chí Minh ký Sắc lệnh 100/SL chấp thuận cho ông Nguyễn Dương từ chức Giám đốc Việt Nam Công an vụ và cử ông Lê Giản lên thay.[5]. Do tình trạng chiến tranh, nhu cầu điều chỉnh cơ cấu tổ chức theo hướng tinh gọn bộ máy để đảm bảo tính cơ động gọn nhẹ, ngày 5 tháng 4 năm 1948, Bộ trưởng Nội vụ Phan Kế Toại ký Nghị định số 291/NĐ tổ chức lại bộ máy ngành Công an[6]. Theo đó Nha Công an Việt Nam đổi tên thành Nha Công an Trung ương. Tên gọi Việt Nam Công an vụ và tổ chức Sở Công an Kỳ không còn sử dụng. Người đứng đầu ngành Công an bấy giờ là ông Lê Giản với chức danh Giám đốc Nha Công an Trung ương. Ngày 6 tháng 9 năm 1952, ông Trần Quốc Hoàn thay Lê Giản làm Giám đốc Nha Công an.[7]
Ngày 16 tháng 2 năm 1953, Nha Công an được nâng cấp thành Thứ bộ Công an thuộc Bộ Nội vụ, do một Thủ trưởng, còn gọi Thứ trưởng Thứ bộ Công an phụ trách[8][9]. Ông Trần Quốc Hoàn giữ chức Thứ trưởng Thứ bộ Công an. Chỉ 6 tháng sau, 27 tháng 8 năm 1953, Bộ Công an được thành lập trên cơ sở Thứ bộ Công an thuộc Bộ Nội vụ, trở thành một bộ riêng biệt[10]. Trần Quốc Hoàn trở thành Bộ trưởng Bộ Công an đầu tiên.
Từ năm 1975 đến 1998, Bộ Công an hợp nhất với Bộ Nội vụ. Chức vụ Bộ trưởng cũng được đổi thành Bộ trưởng Bộ Nội vụ. Từ năm 1998, dùng lại chức danh cũ Bộ trưởng Bộ Công an.
